﻿#pragma once
#include<iostream>
#include<vector>
#include<string>
#include <algorithm>
using namespace std;

enum State
{
	EMPTY, // 空
	EXIST, // 有值
	DELETE // 销毁
};

template<class K, class V>
struct HashData
{
	pair<K,V> _kv;
	State _state = EMPTY; //给每个存储位置一个状态值
};

// 仿函数模版：返回一个可以执行取模运算(%)的数值
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{ // 这里的模版针对char,int,long等整数类别的值,只是单纯的返回原值
		return (size_t)key;
	}
};
// 对于string等容器或自定义类型,无法强转成size_t,就需要自己实现一个特化版本
// 对于自定义类型如struct Date内除了要自主实习仿函数还要支持比较相等！
template<>
struct HashFunc<string>
{
	// 字符串转换成整形，可以把字符ascii码相加即可
	// 但是直接相加的话，类似"ab"和"ba"这样的字符串计算出是相同的
	// 这里我们使用BKDR哈希的思路，用上次的计算结果去乘以一个质数，这个质数一般用31, 131等效果会比较好
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto str : s)
		{
			hash *= 131;
			hash += str;
			// ab : ((97*131)+98)*131 = 1677455
			// ba : ((98*131)+97)*131 = 1694485
		}
		// 这里如果hash整形溢出，对于无符号整数会发生值环绕
		// 类似于取模运算，但并不是显示的(从0重新开始)
		// 注:string的组合数26^16远大于size_t的组合数2^32，有风险性，冲突不可避免！
		return hash;
	}
};

// 扩容
inline unsigned long __stl_next_prime(unsigned long n)
{
	// 注意：假设long至少是32位(long 的大小可能因编译器和平台而异)
	static const int __stl_num_primes = 28;
	static const unsigned long __stl_prime_list[__stl_num_primes] =
	{ // 素数表
		53, 97, 193, 389, 769,
		1543, 3079, 6151, 12289, 24593,
		49157, 98317, 196613, 393241, 786433,
		1572869, 3145739, 6291469, 12582917, 25165843,
		50331653, 100663319, 201326611, 402653189, 805306457,
		1610612741, 3221225473, 4294967291
	};
	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list + __stl_num_primes;
	// lower_bound()是泛型算法，使用前序列必须是有序的
	const unsigned long* pos = lower_bound(first, last, n); // lower_bound()取 >= 
	// 找出上述28个素数中最接近并大于或等于n的那个质数
	return pos == last ? *(last - 1) : *pos;
}

namespace zyt
{
	template<class K,class V,class Hash = HashFunc<K>>
	struct Hashtable
	{
	public:
		Hashtable()
			:_tables(__stl_next_prime(0))
			,_n(0)
		{}		

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;

			// 负载因子 >= 0.7扩容
			if (_n * 10 / _tables.size() >= 7)
			{
				Hashtable<K, V, Hash> newht;
				//newht._tables.resize(_tables.size()*2); // 尽量避免为2的幂
				
				// 一定要强转，不然你想象不到会报什么奇怪的错，气死我了！！！！
				unsigned long len = (unsigned long)_tables.size() + 1;
				size_t newsize = __stl_next_prime(len);
				newht._tables.resize(newsize);

				for (auto& data : _tables)
				{
					// 旧表的数据映射到新表
					if (data._state == EXIST)
					{
						newht.Insert(data._kv);
					}
				}
				// 交换资源
				_tables.swap(newht._tables);
			}

			Hash hash; //仿函数
			size_t hashi = hash(kv.first) % _tables.size(); //算出要插入的下标
			while (_tables[hashi]._state == EXIST)
			{
				// 线性探测
				++hashi;
				hashi %= _tables.size();
			}
			
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			++_n;

			return true;
		}
		 
		// 查找，返回找到的数据
		HashData<K,V>* Find(const K& key)
		{
			Hash hs; //仿函数
			size_t hash0 = hs(key) % _tables.size(); // 除留余数法，算出key映射的下标位置
			size_t hashi = hash0;
			size_t i = 1;
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._state == EXIST
					&& _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];
				}
				// 线性探测
				hashi = (hash0 + i) % _tables.size();
				++i;
			}
			return nullptr;
		}
		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret == nullptr)
				return false;
			else
			{
				ret->_state = DELETE;
				return true;
			}
		}
	private:
		vector<HashData<K, V>> _tables;
		size_t _n; // 哈希表储存元素的个数
	};

}

